#pragma once

#include "iostream"
#include "vector"
#include "algorithm"

using namespace std;
/*HJJ QQ479287006
 *
 * */

//堆排序大顶堆
//这玩意是升序 以为他和最后一个元素交换了 这边是个数组 然后就是升序了自己稍微想一下
void adjust(vector<int> &nums, int len, int index) {
    int left = 2 * index + 1; // index的左子节点
    int right = 2 * index + 2;// index的右子节点
    int maxIdx = index;
    //这边我刚才想错了 因为这个交换肯定是选了父 和两个孩子的最大 然后交换了
    //不用再判断另外一个是不是符合了
    if (left < len && nums[left] > nums[maxIdx]) maxIdx = left;
    if (right < len && nums[right] > nums[maxIdx]) maxIdx = right;
    if (maxIdx != index) {
        swap(nums[maxIdx], nums[index]);
        adjust(nums, len, maxIdx);
    }

}

// 堆排序
void HeapSort(vector<int> &nums, int size) {
    //先调整堆 从叶子节点最后一个的父节点开始
    //大顶堆反而从小到大了
    for (int i = size / 2 - 1; i >= 0; i--) {
        adjust(nums, size, i);
    }

    //交换首尾元素
    for (int i = size - 1; i >= 1; i--) {
        swap(nums[0], nums[i]);
        adjust(nums, i, 0);//这次调整的时候反而从上倒下了
    }

}